{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 【2019】牛客模考（一模）编程题集合 \n",
    "[传送门](https://www.nowcoder.com/test/question/1bc7b0a9a717462ca8386cebb842548f?pid=31380358&tid=49308533)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## python输入输出接口\n",
    "```python\n",
    "import sys \n",
    "for line in sys.stdin:\n",
    "    a = line.split()\n",
    "    print(int(a[0]) + int(a[1]))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1 独立的牛牛\n",
    "1/5\n",
    "[编程题]独立的牛牛\n",
    "时间限制：C/C++ 1秒，其他语言2秒\n",
    "\n",
    "空间限制：C/C++ 32M，其他语言64M\n",
    "\n",
    "小牛牛为了向他的父母表现他已经长大独立了,他决定搬出去自己居住一段时间。\n",
    "\n",
    "一个人生活增加了许多花费: 牛牛每天必须吃一个水果并且需要每天支付x元的房屋租金。\n",
    "\n",
    "当前牛牛手中已经有f个水果和d元钱,牛牛也能去商店购买一些水果,商店每个水果售卖p元。\n",
    "\n",
    "牛牛为了表现他独立生活的能力,希望能独立生活的时间越长越好,牛牛希望你来帮他计算一下他最多能独立生活多少天。\n",
    "\n",
    "\n",
    "输入描述:\n",
    "输入包括一行,四个整数x, f, d, p(1 <= x,f,d,p <= 2 * 10^9),以空格分割\n",
    "\n",
    "输出描述:\n",
    "输出一个整数, 表示牛牛最多能独立生活多少天。\n",
    "\n",
    "输入例子1:\n",
    "3 5 100 10\n",
    "\n",
    "输出例子1:\n",
    "11"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 解析\n",
    "```python\n",
    "import sys\n",
    "\n",
    "for line in sys.stdin:\n",
    "    x, f, d, p = map(int, line.split(' '))\n",
    "    if d // x <= f:\n",
    "        print(d // x)\n",
    "    else:\n",
    "        print(f + (d - f * x) // (p + x))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 牛牛炒股\n",
    "2/5\n",
    "[编程题]牛牛炒股票\n",
    "时间限制：C/C++ 1秒，其他语言2秒\n",
    "\n",
    "空间限制：C/C++ 32M，其他语言64M\n",
    "\n",
    "牛牛得知了一些股票今天买入的价格和明天卖出的价格，他找犇犇老师借了一笔钱，现在他想知道他最多能赚多少钱。\n",
    "\n",
    "输入描述:\n",
    "每个输入包含一个测试用例。\n",
    "输入的第一行包括两个正整数,表示股票的种数N(1<=N<=1000)和牛牛借的钱数M(1<=M<=1000)。\n",
    "接下来N行，每行包含两个正整数，表示这只股票每一股的买入价X(1<=X<=1000)和卖出价Y(1<=Y<=2000)。\n",
    "每只股票可以买入多股，但必须是整数。\n",
    "\n",
    "输出描述:\n",
    "输出一个整数表示牛牛最多能赚的钱数。\n",
    "\n",
    "输入例子1:<br/>\n",
    "3 5 <br/>\n",
    "3 6 <br/>\n",
    "2 3 <br/>\n",
    "1 1 <br/>\n",
    "\n",
    "输出例子1:\n",
    "4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 解析\n",
    "```python\n",
    "import sys\n",
    "from typing import Dict\n",
    "\n",
    "# n: 股票总数, m: 借得的钱数\n",
    "n, m = map(int, sys.stdin.readline().split(' '))\n",
    "stocks = {}\n",
    "\n",
    "for line in sys.stdin:\n",
    "    price, price2 = map(int, line.split(' '))\n",
    "    price_diff = price2 - price\n",
    "    if (price in stocks and stocks[price] < price_diff) or price not in stocks:\n",
    "        if price_diff <= 0:\n",
    "            continue\n",
    "        stocks[price] = price_diff\n",
    "    if len(stocks) >= n:\n",
    "        break\n",
    "\n",
    "\n",
    "def find_best_stock(_stocks: Dict[int, int], _money: int) -> (int, int, int):\n",
    "    if len(_stocks):\n",
    "        return max([(s, _money // s * s, _money // s * p) for s, p in _stocks.items()], key=lambda x: (x[2], -x[1]))\n",
    "    else:\n",
    "        return 0, 0, 0\n",
    "\n",
    "\n",
    "profit = 0\n",
    "money = m\n",
    "while True:\n",
    "    _s, _c, _p = find_best_stock(stocks, money)\n",
    "    if _p <= 0:\n",
    "        print(profit)\n",
    "        break\n",
    "    else:\n",
    "        profit += _p\n",
    "        money -= _c\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 牛牛取快递\n",
    "[编程题]牛牛取快递\n",
    "时间限制：C/C++ 1秒，其他语言2秒\n",
    "\n",
    "空间限制：C/C++ 32M，其他语言64M\n",
    "\n",
    "牛牛的快递到了，他迫不及待地想去取快递，但是天气太热了，以至于牛牛不想在烈日下多走一步。他找来了你，请你帮他规划一下，他最少要走多少距离才能取回快递。\n",
    "\n",
    "输入描述:\n",
    "每个输入包含一个测试用例。\n",
    "输入的第一行包括四个正整数，表示位置个数N(2<=N<=10000)，道路条数M(1<=M<=100000)，起点位置编号S(1<=S<=N)和快递位置编号T(1<=T<=N)。位置编号从1到N，道路是单向的。数据保证S≠T，保证至少存在一个方案可以从起点位置出发到达快递位置再返回起点位置。\n",
    "接下来M行，每行包含三个正整数，表示当前道路的起始位置的编号U(1<=U<=N)，当前道路通往的位置的编号V(1<=V<=N)和当前道路的距离D(1<=D<=1000)。\n",
    "\n",
    "输出描述:\n",
    "对于每个用例，在单独的一行中输出从起点出发抵达快递位置再返回起点的最短距离。\n",
    "\n",
    "输入例子1: <br/>\n",
    "3 3 1 3 <br/>\n",
    "1 2 3 <br/>\n",
    "2 3 3 <br/>\n",
    "3 1 1 <br/>\n",
    "\n",
    "输出例子1:\n",
    "7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 题目解析\n",
    "- 图最短路径算法\n",
    "- 只求两点间来去的两条路径, 适合单源最短路径适合\n",
    "- 点数最高10000, 道路数最高100000, 图的规模可能很大, 注意性能和存储限制\n",
    "- 注意图的自边(起点和终点都是自己)/重边\n",
    "\n",
    "无负权重的边, 采用Dijkstra算法, 提交后发现有两个测试用例超过2s, 对其性能进行优化:\n",
    "- 1)_solved和_not_solved重复, 可以节省一个, 此外采用数组存, 空间相同读取效率要高过in判断\n",
    "- 2)我们不会更新_solved中节点的dist, 因此u==j可以直接return\n",
    "- 3)_not_solved可以使用PriorityQueue排序, 我们可以使用\n",
    "- 4)松弛时只松弛当前找到最优点的邻居节点(未solved的节点), 需要多建一个邻居节点的缓存"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Dijkstra优化算法\n",
    "----\n",
    "假定:\n",
    "1)图任意两点可达\n",
    "2)边权重(距离)大于0\n",
    "\"\"\"\n",
    "import unittest\n",
    "from math import inf, isinf\n",
    "from queue import PriorityQueue\n",
    "\n",
    "\n",
    "def dijkstra(_N: int, _edges: dict, v: int):\n",
    "    \"\"\"\n",
    "    :param _N: 点个数\n",
    "    :param _edges: 边集合  ((起始点id, 结束点id), 距离), 点id取值范围为: {1, 2, ..., _N}\n",
    "    :param v: 计算的点id\n",
    "    :return: 点v到其他个点的最短距离, 点v到其他各点的中转集合\n",
    "    点v到其他个点的最短距离: {点id: 最短距离}\n",
    "    点v到其他各点的中转集合: 格式为{j: u}, 即v到j点需要经过u点, 用于获得最短路径, 是个可变变量\n",
    "    \"\"\"\n",
    "    # 最短距离缓存, 是个可变变量\n",
    "    dist = dict()\n",
    "    # 路径中转, 格式: {j: u}, 即v到j点需要经过u点, 用于获得最短路径, 是个可变变量\n",
    "    transit = {}\n",
    "    # 初始化最短距离缓存\n",
    "    for k in range(1, _N + 1):\n",
    "        if (v, k) in _edges:\n",
    "            dist[k] = _edges[(v, k)]\n",
    "        else:\n",
    "            dist[k] = inf\n",
    "\n",
    "    # 已经找到最优路径的点集合, 可变\n",
    "    _solved = {v}\n",
    "    # 未找到最优路径的点集合, 可变\n",
    "    _not_solved = {i for i in range(1, _N + 1) if i != v}\n",
    "\n",
    "    _cnt = 0\n",
    "    while len(_not_solved) > 0 and _cnt <= _N:\n",
    "        # S1, 从_not_solved中找距离最近的点集, 更新点集\n",
    "        u = -1\n",
    "        dist_of_u = inf\n",
    "        for j in _not_solved:\n",
    "            if dist[j] <= dist_of_u:\n",
    "                u = j\n",
    "                dist_of_u = dist[j]\n",
    "        _solved.add(u)\n",
    "        _not_solved.remove(u)\n",
    "\n",
    "        # S2, 松弛_un_resolved集合中的最短路径\n",
    "        if not isinf(dist_of_u):\n",
    "            for k, _d in dist.items():\n",
    "                if (u, k) in _edges and k not in _solved:\n",
    "                    if _edges[(u, k)] + dist_of_u < _d:\n",
    "                        dist[k] = _edges[(u, k)] + dist_of_u\n",
    "                        transit[k] = u\n",
    "        _cnt += 1\n",
    "    return dist, transit\n",
    "\n",
    "\n",
    "# 效率优化:\n",
    "# 1)_solved和_not_solved重复, 可以节省一个, 此外采用数组存, 空间相同读取效率要高过in判断\n",
    "# 2)我们不会更新_solved中节点的dist, 因此u==j可以直接return\n",
    "# 3)_not_solved可以使用PriorityQueue排序, 我们可以使用\n",
    "# 4)松弛时只松弛当前找到最优点的邻居节点(未solved的节点), 需要多建一个邻居节点的缓存\n",
    "\n",
    "def dijkstra2(_N: int, _edges: dict, v: int, target: int):\n",
    "    \"\"\"\n",
    "    :param target: 目标点id\n",
    "    :param _N: 点个数\n",
    "    :param _edges: 边集合  ((起始点id, 结束点id), 距离), 点id取值范围为: {1, 2, ..., _N}\n",
    "    :param v: 计算的点id\n",
    "    :return: 点v到其他个点的最短距离, 点v到其他各点的中转集合\n",
    "    点v到其他个点的最短距离: {点id: 最短距离}\n",
    "    点v到其他各点的中转集合: 格式为{j: u}, 即v到j点需要经过u点, 用于获得最短路径, 是个可变变量\n",
    "    \"\"\"\n",
    "    # 最短距离缓存, 是个可变变量\n",
    "    dist = [inf for _ in range(0, _N + 1)]\n",
    "    # 路径中转, 格式: {j: u}, 即v到j点需要经过u点, 用于获得最短路径, 是个可变变量\n",
    "\n",
    "    # 邻居节点缓存, 多建一个\n",
    "    adjacency = [[] for _ in range(0, _N + 1)]\n",
    "    for ((s, e), d) in _edges.items():\n",
    "        adjacency[s].append((e, d))\n",
    "\n",
    "    transit = {}\n",
    "    # 初始化最短距离缓存\n",
    "    dist[v] = 0\n",
    "\n",
    "    solved = set()\n",
    "\n",
    "    # 未找到最优路径的点集合, 采用堆排序的方式放入内存, 只放需要探索的点, 可变\n",
    "    _not_solved = PriorityQueue()\n",
    "    _not_solved.put((0, v))\n",
    "\n",
    "    _cnt = 0\n",
    "    while not _not_solved.empty() and _cnt <= _N:\n",
    "        # S1, 从_not_solved中找距离最近的点集, 更新点集\n",
    "        (dist_of_u, u) = _not_solved.get()\n",
    "\n",
    "        # S2, 松弛_un_resolved集合中的最短路径\n",
    "        if u == target:\n",
    "            return dist_of_u, get_path_dijkstra(transit, v, u)\n",
    "\n",
    "        solved.add(u)\n",
    "        neighbors = adjacency[u]\n",
    "        for (e, d) in neighbors:\n",
    "            if e not in solved and dist[e] > dist_of_u + d:\n",
    "                dist[e] = dist_of_u + d\n",
    "                if u != v:\n",
    "                    transit[e] = u\n",
    "                _not_solved.put((dist_of_u + d, e))\n",
    "        _cnt += 1\n",
    "    return None, None\n",
    "\n",
    "\n",
    "def get_path_dijkstra(_transit: dict, _i: int, _j: int) -> list:\n",
    "    \"\"\"\n",
    "    获取图上的路径\n",
    "    :param _transit: 中转矩阵 格式为{j: u}, 即v到j点需要经过u点, 用于获得最短路径, 是个可变变量, 如果j不在其中则表示直接可达\n",
    "    :param _i: Dijkstra算法选定的起始点\n",
    "    :param _j: 目标点\n",
    "    :return: 路径\n",
    "    \"\"\"\n",
    "    if _j in _transit:\n",
    "        pre = get_path_dijkstra(_transit, _i, _transit[_j])\n",
    "        return pre + [_j]\n",
    "    else:\n",
    "        return [_i, _j]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 自测"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "distance: 22, expected distance: 22, trip: 1->3->6->4, expected trip: 1->3->6->4\n",
      "distance: 28, expected distance: 28, trip: 1->3->2->5, expected trip: 1->3->2->5\n",
      "distance: 12, expected distance: 12, trip: 1->3->6, expected trip: 1->3->6\n",
      "distance: 8, expected distance: 8, trip: 1->2->4->3, expected trip: 1->2->4->3\n",
      "distance: 6, expected distance: 6, trip: 1->2->3, expected trip: 1->2->3\n",
      "distance: 3, expected distance: 3, trip: 1->2, expected trip: 1->2\n",
      "dijkstra\n",
      "distance: 22, expected distance: 22, trip: 1->3->6->4, expected trip: 1->3->6->4\n",
      "10 10\n",
      "distance: 28, expected distance: 28, trip: 1->3->2->5, expected trip: 1->3->2->5\n",
      "10 10\n",
      "distance: 12, expected distance: 12, trip: 1->3->6, expected trip: 1->3->6\n",
      "7 7\n",
      "distance: 8, expected distance: 8, trip: 1->2->4->3, expected trip: 1->2->4->3\n",
      "10 10\n",
      "distance: 6, expected distance: 6, trip: 1->2->3, expected trip: 1->2->3\n",
      "7 7\n",
      "distance: 3, expected distance: 3, trip: 1->2, expected trip: 1->2\n",
      "4 4\n"
     ]
    }
   ],
   "source": [
    "import unittest\n",
    "import sys\n",
    "\n",
    "\n",
    "class TestDijkstra(unittest.TestCase):\n",
    "    def test_init(self):\n",
    "        self.input_and_output = [\n",
    "            # N: 表示位置个数N: 2 <= N <= 10000\n",
    "            # M: 道路条数M: 1 <= M <= 100000\n",
    "            # S: 起点位置编号S: 1 <= S <= N\n",
    "            # T: 快递位置编号T: 1 <= T <= N\n",
    "            ('''\n",
    "            6 9 1 4\n",
    "            1 3 5\n",
    "            1 4 30\n",
    "            2 1 2\n",
    "            2 5 8\n",
    "            3 6 7\n",
    "            3 2 15\n",
    "            5 4 4\n",
    "            6 4 10\n",
    "            6 5 18''', 22, '1->3->6->4'),  # 22  1->3->6->4\n",
    "            ('''\n",
    "            6 9 1 5\n",
    "            1 3 5\n",
    "            1 4 30\n",
    "            2 1 2\n",
    "            2 5 8\n",
    "            3 6 7\n",
    "            3 2 15\n",
    "            5 4 4\n",
    "            6 4 10\n",
    "            6 5 18''', 28, '1->3->2->5'),  # 28 1->3->2->5\n",
    "            ('''\n",
    "            6 9 1 6\n",
    "            1 3 5\n",
    "            1 4 30\n",
    "            2 1 2\n",
    "            2 5 8\n",
    "            3 6 7\n",
    "            3 2 15\n",
    "            5 4 4\n",
    "            6 4 10\n",
    "            6 5 18''', 12, '1->3->6'),  # 12 1->3->6\n",
    "            ('''\n",
    "            4 4 1 3\n",
    "            1 2 3\n",
    "            2 4 3\n",
    "            4 3 2\n",
    "            3 1 1''', 8, '1->2->4->3'),\n",
    "            ('''\n",
    "            3 3 1 3\n",
    "            1 2 3\n",
    "            2 3 3\n",
    "            3 1 1''', 6, '1->2->3'),\n",
    "            ('''\n",
    "            2 2 1 2\n",
    "            1 2 3\n",
    "            2 1 3''', 3, '1->2')\n",
    "        ]\n",
    "\n",
    "    def test_1dijkstra(self):\n",
    "        self.test_init()\n",
    "        for info, expected_distance, expected_trip in self.input_and_output:\n",
    "            information = [each.strip() for each in info.splitlines() if len(each.strip()) > 0]\n",
    "            _N, _M, _S, _T = map(int, information[0].split(' '))\n",
    "            # 边\n",
    "            edges = {}\n",
    "            cnt = 0\n",
    "            for line in information[1:]:\n",
    "                s, e, d = map(int, line.split(' '))\n",
    "                edges[(s, e)] = d\n",
    "                cnt += 1\n",
    "                if cnt >= _M:\n",
    "                    break\n",
    "\n",
    "            _dist, _transit = dijkstra(_N, edges, _S)\n",
    "            distance = _dist[_T]\n",
    "            trip = '->'.join([str(each) for each in get_path_dijkstra(_transit, _S, _T)])\n",
    "\n",
    "            print('distance: %d, expected distance: %d, trip: %s, expected trip: %s' %\n",
    "                  (distance, expected_distance, trip, expected_trip))\n",
    "            assert distance == expected_distance\n",
    "            assert trip == expected_trip\n",
    "\n",
    "    def test_dijkstra2(self):\n",
    "        self.test_init()\n",
    "        print(\"dijkstra\")\n",
    "        for info, expected_distance, expected_trip in self.input_and_output:\n",
    "            information = [each.strip() for each in info.splitlines() if len(each.strip()) > 0]\n",
    "            _N, _M, _S, _T = map(int, information[0].split(' '))\n",
    "            # 边\n",
    "            edges = {}\n",
    "            cnt = 0\n",
    "            for line in information[1:]:\n",
    "                s, e, d = map(int, line.split(' '))\n",
    "                if ((s, e) in edges and edges[(s, e)] > d) or (s, e) not in edges:\n",
    "                    if s == e:\n",
    "                        continue\n",
    "                    edges[(s, e)] = d\n",
    "                cnt += 1\n",
    "                if cnt >= _M:\n",
    "                    break\n",
    "\n",
    "            distance, trip_nodes = dijkstra2(_N, edges, _S, _T)\n",
    "            trip = '->'.join(map(str, trip_nodes))\n",
    "            print('distance: %d, expected distance: %d, trip: %s, expected trip: %s' %\n",
    "                  (distance, expected_distance, trip, expected_trip))\n",
    "            assert distance == expected_distance\n",
    "            print(len(trip), len(expected_trip))\n",
    "            assert trip == expected_trip\n",
    "\n",
    "\n",
    "sys.setrecursionlimit(100000)  # 设置递归深度\n",
    "TestDijkstra().test_1dijkstra()\n",
    "TestDijkstra().test_dijkstra2()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 解答\n",
    "```python\n",
    "import sys\n",
    "from math import inf\n",
    "from queue import PriorityQueue\n",
    "\n",
    "\n",
    "def dijkstra2(_N: int, _edges: dict, v: int, target: int):\n",
    "    \"\"\"\n",
    "    :param target: 目标点id\n",
    "    :param _N: 点个数\n",
    "    :param _edges: 边集合  ((起始点id, 结束点id), 距离), 点id取值范围为: {1, 2, ..., _N}\n",
    "    :param v: 计算的点id\n",
    "    :return: 点v到其他个点的最短距离, 点v到其他各点的中转集合\n",
    "    点v到其他个点的最短距离: {点id: 最短距离}\n",
    "    点v到其他各点的中转集合: 格式为{j: u}, 即v到j点需要经过u点, 用于获得最短路径, 是个可变变量\n",
    "    \"\"\"\n",
    "    # 最短距离缓存, 是个可变变量\n",
    "    dist = [inf for _ in range(0, _N + 1)]\n",
    "    # 路径中转, 格式: {j: u}, 即v到j点需要经过u点, 用于获得最短路径, 是个可变变量\n",
    "\n",
    "    # 邻居节点缓存, 多建一个\n",
    "    adjacency = [[] for _ in range(0, _N + 1)]\n",
    "    for ((s, e), d) in _edges.items():\n",
    "        adjacency[s].append((e, d))\n",
    "\n",
    "    transit = {}\n",
    "    # 初始化最短距离缓存\n",
    "    dist[v] = 0\n",
    "\n",
    "    solved = set()\n",
    "\n",
    "    # 未找到最优路径的点集合, 采用堆排序的方式放入内存, 只放需要探索的点, 可变\n",
    "    _not_solved = PriorityQueue()\n",
    "    _not_solved.put((0, v))\n",
    "\n",
    "    _cnt = 0\n",
    "    while not _not_solved.empty():\n",
    "        # S1, 从_not_solved中找距离最近的点集, 更新点集\n",
    "        (dist_of_u, u) = _not_solved.get()\n",
    "\n",
    "        # S2, 松弛_un_resolved集合中的最短路径\n",
    "        if u == target:\n",
    "            return dist_of_u, get_path_dijkstra(transit, v, u)\n",
    "\n",
    "        solved.add(u)\n",
    "        neighbors = adjacency[u]\n",
    "        for (e, d) in neighbors:\n",
    "            if e not in solved and dist[e] > dist_of_u + d:\n",
    "                dist[e] = dist_of_u + d\n",
    "                if u != v:\n",
    "                    transit[e] = u\n",
    "                _not_solved.put((dist_of_u + d, e))\n",
    "        _cnt += 1\n",
    "    return None, None\n",
    "\n",
    "\n",
    "def get_path_dijkstra(_transit: dict, _i: int, _j: int) -> list:\n",
    "    \"\"\"\n",
    "    获取图上的路径\n",
    "    :param _transit: 中转矩阵 格式为{j: u}, 即v到j点需要经过u点, 用于获得最短路径, 是个可变变量, 如果j不在其中则表示直接可达\n",
    "    :param _i: Dijkstra算法选定的起始点\n",
    "    :param _j: 目标点\n",
    "    :return: 路径\n",
    "    \"\"\"\n",
    "    if _j in _transit:\n",
    "        pre = get_path_dijkstra(_transit, _i, _transit[_j])\n",
    "        return pre + [_j]\n",
    "    else:\n",
    "        return [_i, _j]\n",
    "\n",
    "\n",
    "sys.setrecursionlimit(100000)\n",
    "line = sys.stdin.readline()\n",
    "_N, _M, _S, _T = [int(each.strip()) for each in line.split(' ')[:4]]\n",
    "# 边\n",
    "edges = {}\n",
    "cnt = 0\n",
    "for line in sys.stdin:\n",
    "    s, e, d = map(int, line.split(' ')[:3])\n",
    "    if ((s, e) in edges and edges[(s, e)] > d) or (s, e) not in edges:\n",
    "        if s == e:\n",
    "            continue\n",
    "        edges[(s, e)] = d\n",
    "    cnt += 1\n",
    "    if cnt >= _M:\n",
    "        break\n",
    "\n",
    "distance, trip_nodes = dijkstra2(_N, edges, _S, _T)\n",
    "distance2, trip_nodes2 = dijkstra2(_N, edges, _T, _S)\n",
    "print(distance + distance2)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  3.4 讨论\n",
    "#### 3.4.1 调试\n",
    "- 在牛客调试的时候，运行时间出错不会在前端显示，但通过浏览器network看到了\n",
    "- python3包了最大迭代次数超限，用python2没出现这个错误，搜了下发现需要setrecursionlimit\n",
    "\n",
    "\n",
    "#### 3.4.2 参考\n",
    "图论算法理论、实现及应用 | 第4章 最短路径问题\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4 牛牛打响指\n",
    "4/5\n",
    "[编程题]牛牛打响指\n",
    "时间限制：C/C++ 1秒，其他语言2秒\n",
    "\n",
    "空间限制：C/C++ 32M，其他语言64M\n",
    "\n",
    "牛牛在地上捡到了一个手套，他带上手套发现眼前出现了很多个小人，当他打一下响指，这些小人的数量就会发生以下变化：如果小人原本的数量是偶数那么数量就会变成一半，如果小人原本的数量是奇数那么数量就会加一。现在牛牛想考考你，他要打多少次响指，才能让小人的数量变成1。\n",
    "\n",
    "输入描述:\n",
    "每个输入包含一个测试用例。\n",
    "输入的第一行包括一个正整数，表示一开始小人的数量N(1<=N<=10^100)。\n",
    "\n",
    "输出描述:\n",
    "对于每个用例，在单独的一行中输出牛牛需要打多少次响指才能让小人的数量变成1。\n",
    "\n",
    "输入例子1:\n",
    "10000\n",
    "\n",
    "输出例子1:\n",
    "20"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 解析\n",
    "超过100位的整数除法(除以2)，python float在18位的时候就出现了舍入导致不精确的问题。因此需要手动写一个基于各个位的除法。\n",
    "\n",
    "### 4.2 解答\n",
    "```python\n",
    "import sys\n",
    "from typing import List\n",
    "\n",
    "\n",
    "def is_odd(_num_list: List[int]):\n",
    "    return _num_list[-1] % 2 != 0\n",
    "\n",
    "\n",
    "def divided_by_2(_num_list: List[int]):\n",
    "    mod_res = 0\n",
    "    res = []\n",
    "    not_met_fist = True\n",
    "    for each in _num_list:\n",
    "        consult = mod_res * 5 + each // 2\n",
    "        mod_res = each % 2\n",
    "        if not_met_fist:\n",
    "            if consult != 0:\n",
    "                not_met_fist = False\n",
    "                res.append(consult)\n",
    "        else:\n",
    "            res.append(consult)\n",
    "    return res\n",
    "\n",
    "\n",
    "line = sys.stdin.readline()\n",
    "num = [int(each) for each in list(line.strip())]\n",
    "cnt = 0\n",
    "\n",
    "while True:\n",
    "    if num == [1]:\n",
    "        print(cnt)\n",
    "        break\n",
    "    if is_odd(num):\n",
    "        num[-1] += 1\n",
    "    else:\n",
    "        num = divided_by_2(num)\n",
    "    cnt += 1\n",
    "\n",
    "```\n",
    "\n",
    "### 4.3 自测实例\n",
    "920193896655629398 => 89 <br/>\n",
    "10000 => 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
